package com.xyz.study.algorithms;

/**
 * TODO
 *
 * @author XYZ
 * @version 1.0
 * @since 2021/4/20 18:42
 */
public class AlgorithmsDay20210420 {
    /**
     * 朴素算法 自己写的
     */
    class Solution1 {
        public int strStr(String haystack, String needle) {
            if(null == haystack || null == needle){
                return -1;
            }
            if (haystack.equals(needle)){
                return 0;
            }
            int haystackLength = haystack.length();
            int needleLength = needle.length();
            if (haystackLength < needleLength){
                return -1;
            }
            for(int i = 0; i < haystackLength - needleLength; i++){
                if(needle.equals(haystack.substring(i, i + needleLength))){
                    return i;
                }
            }
            return -1;
        }
    }

    /**
     * KMP算法
     */
    class Solution2 {
        public int strStr(String ss, String pp) {
            int n = ss.length(), m = pp.length();
            char[] s = ss.toCharArray(), p = pp.toCharArray();
            // 枚举原串的「发起点」
            for (int i = 0; i <= n - m; i++) {
                // 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
                int a = i, b = 0;
                while (b < m && s[a] == p[b]) {
                    a++;
                    b++;
                }
                // 如果能够完全匹配，返回原串的「发起点」下标
                if (b == m) return i;
            }
            return -1;
        }
    }
}
